package alibabainterview.cardproblem;

import java.util.Scanner;

/*
 * 卡牌问题
 * 问题描述：n副卡牌，每副 m 张牌，编号 1 到 m；现在每副牌中抽出一张，选出来的卡牌编号之和恰好为k
 * 问：有多少种选择方案，对10^9+7取余
 * 第一行 T 组测试数据
 * 第一组的第一行，n副牌，每副m张牌，编号目标和k
 * 输出方案数量
 */
public class Main {
    static int res = 0;
    public static void main(String[] args){
        // 先进行输入数据的读取
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 几组测试数据
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();
            System.out.println(numOfPlans(n,m,k));
        }
    }
    public static int numOfPlans(int n, int m, int k){
        // n副牌，编号1-m，目标和k
        // dp[n][k] n副牌，目标为k的情况下组合数
        int[][] dp = new int[n+1][k+1];
        for (int i = 1; i <= n; i++) { // i副牌
            for (int j = 1; j <= k; j++) { // 目标为j
                if(i == 1){ // 只有1副牌
                    if(j<=m){ // 如果当前的目标小于牌的最大编号
                        dp[i][j] = 1;
                    }
                }
                // 选择其中1个编号
                for (int d = 1; d <= m; d++) {
                    if(j-d>0){ // 目标值-当前选的编号大于0
                        dp[i][j] = dp[i][j] + dp[i-1][j-d]; // 相当于用i-1副牌，中目标为j-d,把这个后面的牌的情况都加起来
                    }
                }
            }
        }
        return dp[n][k];
    }
}
